
//这里目的是判断某个队伍是否已经在数学上被淘汰掉了
//两种判断情况，一种是简单淘汰，也就是如果x 队获胜的最大场次少于其他某个i队获胜的场次，
//则 x 队将被简单淘汰（如上例中的蒙特利尔队）。也就是说，如果w[x]+ r[x]< w[i]，则从数学上讲x队将被淘汰
//另一种是不简单的，也就是最大流去判断，我们用队伍和队伍之间的比赛和队伍作为点作出二分图，然后设置st点，s到比赛之间的容量为这两个队伍比赛的次数
//队伍到t之间容量，x队的容量为w[x] + r[x]，其他队的容量为 w[x] + r[x] - w[i]
//如果 maxflow 中从s 指向的所有边都已满，则这相当于将获胜者分配给所有剩余比赛，使得没有一支球队赢得的比赛比x多。
//如果从s指向的一些边未满，则不存在x队赢得分区冠军的情况。
//一支球队剩余的比赛场次不一定等于与其所在赛区球队比赛场次的总和，因为一支球队可能会与所在赛区以外的球队比赛
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import edu.princeton.cs.algs4.FordFulkerson;
import edu.princeton.cs.algs4.FlowEdge;
import edu.princeton.cs.algs4.FlowNetwork;

import edu.princeton.cs.algs4.In;

public class BaseballElimination {
    // 用编号对应，比如0是底特律，那么其他数组的0位置也都是底特律相关数据
    private ArrayList<String> team;
    private int[] win;
    private int[] losses;
    private int[] remaining;
    private int[][] against;

    // 通过文件名初始化
    public BaseballElimination(String filename) // create a baseball division from given filename in format specified
                                                // below
    {
        In in = new In(filename);
        if (in.isEmpty()) {
            throw new IllegalArgumentException("null input");
        }
        int i = in.readInt(); // 有几个队伍
        team = new ArrayList<String>(i);
        win = new int[i];
        losses = new int[i];
        remaining = new int[i];
        against = new int[i][i];
        for (int j = 0; j < i; j++) {
            team.add(in.readString());
            win[j] = in.readInt();
            losses[j] = in.readInt();
            remaining[j] = in.readInt();
            for (int k = 0; k < i; k++) {
                against[j][k] = in.readInt();
            }
        }
    }

    // 队伍的数量
    public int numberOfTeams() // number of teams
    {
        return team.size();
    }

    // 返回所有的队伍
    public Iterable<String> teams() // all teams
    {
        return team;
    }

    // 一个队伍的胜利数
    public int wins(String team) // number of wins for given team
    {
        int i = team.indexOf(team);
        return win[i];
    }

    // 一个队伍的失败数
    public int losses(String team) // number of losses for given team
    {
        int i = team.indexOf(team);
        return losses[i];
    }

    // 一个队伍的剩余比赛数目
    public int remaining(String team) // number of remaining games for given team
    {
        int i = team.indexOf(team);
        return remaining[i];
    }

    // 队伍1和队伍2的剩余比赛场次
    public int against(String team1, String team2) // number of remaining games between team1 and team2
    {
        int i = team.indexOf(team1);
        int j = team.indexOf(team2);
        return against[i][j];
    }

    // 给定队伍是否被淘汰？
    public boolean isEliminated(String team) // is given team eliminated?
    {
        int num = this.team.size();
        int cur = this.team.indexOf(team); // 当前队伍的索引
        // 先进行简单判断
        // 对每一个队伍进行判断
        for (int i = 0; i < num; i++) {
            if (win[cur] + remaining[cur] < win[i]) {
                return true;
            }
        }

        // 如果上面没有判断出会被淘汰则用最大流量进行判断
        FlowNetwork g = new FlowNetwork(this.team.size() * (this.team.size() - 1) / 2 + this.team.size() + 2); // 创建对应队伍的最大流量图
                                                                                                               // 需要比赛数加队伍数，加st点
        
        int gameOfNum=0;                                                                                                       
        // 下面0-n-1表示队伍，再后面n到(n^2-n)/2+n-1是比赛，然后最后两个是st,s-(n^2-n)/2+n,t-(n^2-n)/2+n+1
        // s到各个比赛的边
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                g.addEdge(new FlowEdge((num * num - num) / 2 + num, i * (2 * num - i - 1) / 2 + (j - i - 1) + num,
                        against[i][j]));
                gameOfNum+=against[i][j];
            }
        }

        // 各个比赛到各个队伍的边
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                g.addEdge(new FlowEdge(i * (2 * num - i - 1) / 2 + (j - i - 1) + num, i, Double.POSITIVE_INFINITY));
                g.addEdge(new FlowEdge(i * (2 * num - i - 1) / 2 + (j - i - 1) + num, j, Double.POSITIVE_INFINITY));
            }
        }

        // 各个队伍到t的边
        for (int i = 0; i < num; i++) {
            g.addEdge(new FlowEdge(i, (num * num - num) / 2 + num + 1, win[cur] + remaining[cur] - win[i]));
        }
        FordFulkerson maxflow=new FordFulkerson(g, (num * num - num) / 2 + num, (num * num - num) / 2 + num+1);
        return !(gameOfNum==maxflow.value());        //相等说明没被淘汰，返回false
    }

    

    // 返回淘汰队伍的子集R，如果没有被淘汰返回null
    public Iterable<String> certificateOfElimination(String team) // subset R of teams that eliminates given team; null
                                                                  // if not eliminated
    {
        ArrayList<String> subR=new ArrayList<String>();
        int num = this.team.size();
        int cur = this.team.indexOf(team); // 当前队伍的索引
        // 先进行简单判断
        // 对每一个队伍进行判断
        for (int i = 0; i < num; i++) {
            if (win[cur] + remaining[cur] < win[i]) {
                subR.add(this.team.get(i));
                return subR;
            }
        }

        // 如果上面没有判断出会被淘汰则用最大流量进行判断
        FlowNetwork g = new FlowNetwork(this.team.size() * (this.team.size() - 1) / 2 + this.team.size() + 2); // 创建对应队伍的最大流量图
                                                                                                               // 需要比赛数加队伍数，加st点
        
        int gameOfNum=0;                                                                                                       
        // 下面0-n-1表示队伍，再后面n到(n^2-n)/2+n-1是比赛，然后最后两个是st,s-(n^2-n)/2+n,t-(n^2-n)/2+n+1
        // s到各个比赛的边
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                g.addEdge(new FlowEdge((num * num - num) / 2 + num, i * (2 * num - i - 1) / 2 + (j - i - 1) + num,
                        against[i][j]));
                gameOfNum+=against[i][j];
            }
        }

        // 各个比赛到各个队伍的边
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                g.addEdge(new FlowEdge(i * (2 * num - i - 1) / 2 + (j - i - 1) + num, i, Double.POSITIVE_INFINITY));
                g.addEdge(new FlowEdge(i * (2 * num - i - 1) / 2 + (j - i - 1) + num, j, Double.POSITIVE_INFINITY));
            }
        }

        // 各个队伍到t的边
        for (int i = 0; i < num; i++) {
            g.addEdge(new FlowEdge(i, (num * num - num) / 2 + num + 1, win[cur] + remaining[cur] - win[i]));
        }
        FordFulkerson maxflow=new FordFulkerson(g, (num * num - num) / 2 + num, (num * num - num) / 2 + num+1);
        if(gameOfNum==maxflow.value())    //没被淘汰
        {
           return null;
        }
        else
        {
           for(int i=0;i<num;i++)
           {
            if(maxflow.inCut(i))
            {
                subR.add(this.team.get(i));
            }
           }
           return subR;
        }
    }

    public static void main(String[] args) {
        BaseballElimination division = new BaseballElimination("teams5.txt");
        StdOut.println(division.wins("New_York"));
        for (String team : division.teams()) {
        // if (division.isEliminated(team)) {
        // StdOut.print(team + " is eliminated by the subset R = { ");
        // for (String t : division.certificateOfElimination(team)) {
        // StdOut.print(t + " ");
        // }
        // StdOut.println("}");
        // }
        // else {
        // StdOut.println(team + " is not eliminated");
        // } 
        }
    }
}
